package com.cat.slidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
*   @description https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
*   @author 曲大人的喵
*   @create 2025/9/16 21:35
*   @since JDK17
*/

public class Solution32 {
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLen = words[0].length(), n = s.length();
        int totalLen = wordLen * words.length, m = s.length() - totalLen;
        HashMap<String, Integer> cnt = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        for (var word : words) {    // 记录words
            cnt.merge(word, 1, Integer::sum);
        }

        for (int i = 0; i < m; i++) {
            HashMap<String, Integer> temp = new HashMap<>();
            int debt = words.length;    // 欠了这么多个
            for (int r = i + wordLen, l = i; r < n; r += wordLen) {    // 一次遍历一个单词
                String t = s.substring(r - wordLen, r); // 取出一个单词
                temp.merge(t, 1, Integer::sum);
                if (temp.get(t) <= cnt.getOrDefault(t, 0)) {
                    debt--; // 还了一个
                }
                if (r - l > totalLen) {    // 吐出一个
                    t = s.substring(l, l + wordLen);
                    temp.merge(t, -1, Integer::sum);
                    if (temp.get(t) < cnt.getOrDefault(t, 0)) {
                        debt++; // 拿了一个回去
                    }
                }
                if (debt == 0) {    // 凑出了一个答案
                    ans.add(l);
                }
            }
        }

        return ans;
    }
}
